home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1 Issue 2 / PDCD-1 - Issue 02.iso / _utilities / utilities / 003 / _gs / !GS / c / GSIM2OUT < prev    next >
Text File  |  1991-10-26  |  13KB  |  401 lines
  1. /* Copyright (C) 1989, 1990 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gsim2out.c */
  21. /* Image to outline conversion for GhostScript library */
  22. #include "gx.h"
  23. #include "memory_.h"
  24. #include "gserrors.h"
  25. #include "gsmatrix.h"
  26. #include "gsstate.h"
  27. #include "gscoord.h"
  28. #include "gxfixed.h"
  29. #include "gxtype1.h"
  30.  
  31. /*
  32.  * Convert a bitmap image to an outline (path) representation.
  33.  * The outline representation is in Adobe Type 1 CharString format.
  34.  * See ghost.doc for more details.
  35.  */
  36.  
  37. /* Define the state of the conversion process. */
  38. typedef struct {
  39.     /* The following are set at the beginning of the conversion. */
  40.     gs_matrix ifm;            /* inverse of (CTM */
  41.                     /* scaled by width/height * 4). */
  42.     byte *limit;            /* stop output here */
  43.     int ox, oy;            /* X/Y pixel offset of char origin */
  44.     /* The following are updated dynamically. */
  45.     byte *next;            /* next byte goes here */
  46.     int px, py;            /* X/Y position at start of run */
  47.     int cpx, cpy;            /* px/py in character coordinates */
  48.     int dx, dy;            /* X/Y increment of current run */
  49.     int count;            /* # of steps in current run */
  50. } status;
  51.  
  52. /* Define the scaling for the path tracer. */
  53. #define outline_scale 4
  54.  
  55. /* Forward declarations */
  56. private int round_coord(P1(floatp));
  57. private int put_int(P2(status *, int));
  58. private void fill_cells(P4(byte *, byte *, int, int));
  59. private int trace_cells(P4(byte *, int, int, status *));
  60.  
  61. /*
  62.  * gs_type1imagepath encodes an image into a byte string supplied
  63.  * by the caller.  If the string is not big enough, the procedure
  64.  * returns gs_error_limitcheck.  Otherwise, the procedure returns
  65.  * the actual number of bytes of data stored.
  66.  */
  67. int
  68. gs_type1imagepath(gs_state *pgs, byte *data, int width, int height,
  69.   floatp wx, floatp wy, floatp origin_x, floatp origin_y,
  70.   byte *str, uint maxlen)
  71. {    uint csize;
  72.     byte *cells;
  73.     status stat;
  74.     status *out = &stat;
  75.     int lsbx;
  76.     int iwx, iwy, ilsbx, ilsby;
  77.     int code;
  78.     /* Construct the coordinate transformation. */
  79.        {    float hsc = height * outline_scale;
  80.         gs_matrix mat;
  81.         gs_currentmatrix(pgs, &stat.ifm);
  82. #ifdef DEBUG
  83. if ( gs_debug['0'] )
  84.         dprintf6("[0]ctm=[%g %g %g %g %g %g]\n",
  85.              stat.ifm.xx, stat.ifm.xy, stat.ifm.yx, stat.ifm.yy,
  86.              stat.ifm.tx, stat.ifm.ty);
  87. #endif
  88.         if (    (code = gs_make_scaling(hsc, hsc, &mat)) < 0 ||
  89.             (code = gs_matrix_multiply(&mat, &stat.ifm, &stat.ifm)) < 0 ||
  90.             (code = gs_matrix_invert(&stat.ifm, &stat.ifm)) < 0
  91.            )
  92.             return code;
  93.        }
  94.     /* Allocate and fill in the cell matrix. */
  95.     csize = (width + 2) * (height + 2);
  96.     cells = (byte *)gs_malloc(csize, 1, "gsim2out cells");
  97.     if ( cells == 0 ) return_error(gs_error_VMerror);
  98.     fill_cells(cells, data, width, height);
  99.     /* Initialize the rest of the state. */
  100.     stat.next = str;
  101.     stat.limit = str + maxlen;
  102.     /* Determine the left side bearing by looking for */
  103.     /* the leftmost column with any 1-bits. */
  104.     for ( lsbx = 0; lsbx < width; lsbx++ )
  105.        {    int y;
  106.         for ( y = 1; y <= height; y++ )
  107.           if ( cells[y * (width + 2) + lsbx + 1] ) goto xit;
  108.        }
  109. xit:    /* Encode the origin, width, and side bearing. */
  110.        {    gs_point opt, wpt, lsbpt;
  111.         if (    (code = gs_distance_transform(origin_x * outline_scale,
  112.                               origin_y * outline_scale,
  113.                               &stat.ifm, &opt)) < 0 ||
  114.             (code = gs_distance_transform(wx * outline_scale,
  115.                               wy * outline_scale,
  116.                               &stat.ifm, &wpt)) < 0 ||
  117.             (code = gs_distance_transform((lsbx - origin_x) *
  118.                                outline_scale, (floatp)0,
  119.                               &stat.ifm, &lsbpt)) < 0
  120.            )
  121.             return code;
  122.         stat.ox = round_coord(opt.x);
  123.         stat.oy = round_coord(opt.y);
  124.         iwx = round_coord(wpt.x);
  125.         iwy = round_coord(wpt.y);
  126.         ilsbx = round_coord(lsbpt.x);
  127.         ilsby = round_coord(lsbpt.y);
  128. #ifdef DEBUG
  129. if ( gs_debug['0'] )
  130.        {    int cy, cx;
  131.         byte *cp = data;
  132.         dprintf6("[0]w=%d h=%d oxy=(%g,%g) wxy=(%g,%g)\n",
  133.              width, height, origin_x, origin_y, wx, wy);
  134.         dprintf6("   io=(%d,%d) iw=(%d,%d) ilsb=(%d,%d)\n",
  135.              stat.ox, stat.oy, iwx, iwy, ilsbx, ilsby);
  136.         for ( cy = 0; cy < height; cy++ )
  137.            {    dprintf1("[0]%3d ", cy);
  138.             for ( cx = 0; cx < width; cx += 8 )
  139.                 dprintf1("%02x", (int)*cp++);
  140.             dputc('\n');
  141.            }
  142.        }
  143. #endif
  144.         if ( (code = put_int(out, ilsbx)) < 0 ) return code;
  145.         if ( iwy != 0 || ilsby != 0 )
  146.            {    if (    (code = put_int(out, ilsby)) < 0 ||
  147.                 (code = put_int(out, iwx)) < 0 ||
  148.                 (code = put_int(out, iwy)) < 0
  149.                )
  150.                 return code;
  151.             if ( stat.next + 2 > stat.limit )
  152.                 return_error(gs_error_limitcheck);
  153.             *stat.next++ = (byte)c_escape;
  154.             *stat.next++ = (byte)ce_sbw;
  155.            }
  156.         else
  157.            {    if ( (code = put_int(out, iwx)) < 0 ) return code;
  158.             if ( stat.next + 1 > stat.limit )
  159.                 return_error(gs_error_limitcheck);
  160.             *stat.next++ = (byte)c_hsbw;
  161.            }
  162.        }
  163.     /* Since all further movements are relative, we can account */
  164.     /* for the origin by simply setting px/py to the lsb, */
  165.     /* and cpx/cpy to the lsb plus the origin. */
  166.     stat.px = (lsbx * outline_scale);
  167.     stat.py = (int)(origin_y * outline_scale);
  168.     stat.cpx = ilsbx + stat.ox;
  169.     stat.cpy = ilsby + stat.oy;
  170.     /* Trace the outline of the cells. */
  171.     code = trace_cells(cells, width, height, out);
  172.     gs_free((char *)cells, csize, 1, "gsim2out cells");
  173.     if ( code < 0 ) return code;
  174.     if ( stat.next >= stat.limit ) return_error(gs_error_limitcheck);
  175.     *stat.next++ = (byte)c_endchar;
  176.     return stat.next - str;
  177. }
  178.  
  179. /* Fill the cell matrix with the image being traced. */
  180. /* The cell matrix has a row and column of zero padding on each side, */
  181. /* so we don't have to check for boundary conditions all the time. */
  182. /* Note that the image data are in PostScript / Ghostscript standard */
  183. /* order (left to right, top row first), but the cells are stored */
  184. /* bottom row first. */
  185. private void
  186. fill_cells(byte *cells, byte *data, int width, int height)
  187. {    int y;
  188.     byte *dptr = data - 1;
  189.     byte *cptr = cells + (width + 2) * height + 1;
  190.     memset(cells, 0, (width + 2) * (height + 2));
  191.     for ( y = 0; y < height; y++ )
  192.        {    register int mask = 0;
  193.         register int b;
  194.         register int x;
  195.         for ( x = 0; x < width; x++, mask >>= 1, cptr++ )
  196.            {    if ( mask == 0 ) mask = 0x80, b = *++dptr;
  197.             if ( b & mask ) *cptr = 1;
  198.            }
  199.         cptr -= width * 2 + 2;    /* back up 1 row */
  200.        }
  201. }
  202.  
  203. /* Trace the cells to form an outline.  The trace goes in clockwise */
  204. /* order, always starting by going west along a bottom edge. */
  205. /* All the subsidiary routines return 0 on success, */
  206. /* -1 if the output buffer overflowed. */
  207. private int trace_from(P3(status *, byte *, int));
  208. private int add_dxdy(P4(status *, int, int, int));
  209. #define add_deltas(s, dx, dy, n)\
  210.   if ( (code = add_dxdy(s, dx, dy, n)) < 0 ) return code
  211. private int put_dxdy(P4(status *, int, int, int));
  212. #define put_deltas(s, dx, dy, moving)\
  213.   if ( (code = put_dxdy(s, dx, dy, moving)) < 0 ) return code
  214. private int
  215. trace_cells(byte *cells, int width, int height, register status *out)
  216. {    byte *cptr;
  217.     int code;
  218.     for ( cptr = cells + (width + 2) * (height + 1) - 2;
  219.           cptr >= cells;  cptr--
  220.         )
  221.        {    if ( *cptr == 1 && cptr[-(width+2)] == 0 )
  222.            {    /* Found a starting point */
  223.             int x = (cptr-cells) % (width+2) - 1;
  224.             int y = (cptr-cells) / (width+2) - 1;
  225.             put_deltas(out,
  226.                    x * outline_scale + 1 - out->px,
  227.                    y * outline_scale - out->py,
  228.                    1);
  229.             out->count = 0;
  230.             if ( (code = trace_from(out, cptr, width)) < 0 )
  231.                 return code;
  232.             if ( out->next >= out->limit )
  233.                 return_error(gs_error_limitcheck);
  234.             *out->next++ = (byte)c_closepath;
  235.            }
  236.        }
  237.     return 0;
  238. }
  239.  
  240. /* Trace a path */
  241. private int
  242. trace_from(register status *out, byte *cptr, int width)
  243. {    typedef enum {            /* must be in this order */
  244.         north = 0, east = 1, south = 2, west = 3
  245.     } direction;
  246.     direction dir;
  247.     int w2 = width + 2;        /* actual width of cell rows */
  248.     int part;            /* how far along edge we are */
  249.     int code;
  250.     /* Movement tables */
  251.     typedef struct {
  252.         short tx, ty;        /* relative index of first cell */
  253.                     /* to test (counter-clockwise move) */
  254.         short dx, dy;        /* continue in same direction */
  255.        } dir_descr;
  256.     static dir_descr nesw[4+1] =
  257.        {    /* Going north (along a western edge) */
  258.            { -1, 1,   0, 1 },
  259.         /* Going east (along a northern edge) */
  260.             { 1, 1,   1, 0 },
  261.         /* Going south (along an eastern edge) */
  262.            { 1, -1,   0, -1 },
  263.         /* Going west (along a southern edge) */
  264.            { -1, -1,   -1, 0 },
  265.         /* An extra copy of north */
  266.            { -1, 1,   0, 1 }
  267.        };
  268.     for ( dir = west, part = 1; ; )
  269.        {    register dir_descr *pd = &nesw[(int)dir];
  270.         int dx = pd->dx, dy = pd->dy;
  271.         int delta;
  272.         if ( dir == west )
  273.            {    /* This is the only case that has to check */
  274.             /* for the end of a subpath. */
  275.             if ( *cptr == 2 ) return 0;
  276.             *cptr = 2;
  277.            }
  278.         delta = pd->ty * w2 + pd->tx;
  279.         if ( cptr[delta] )    /* go counter-clockwise */
  280.            {    cptr += delta;
  281.             add_deltas(out, dx, dy, 1 - part);
  282.             add_deltas(out, pd->tx, pd->ty, outline_scale - 1);
  283.             dir = (direction)(((int)dir - 1) & 3);
  284.             part = outline_scale - 1;
  285.             continue;
  286.            }
  287.         delta = dy * w2 + dx;
  288.         if ( !cptr[delta] )    /* go clockwise */
  289.            {    add_deltas(out, dx, dy, outline_scale - 1 - part);
  290.             add_deltas(out, dx + pd[1].dx, dy + pd[1].dy, 1);
  291.             dir = (direction)(((int)dir + 1) & 3);
  292.             part = 1;
  293.             continue;
  294.            }
  295.         cptr += delta;        /* go in same direction */
  296.         add_deltas(out, dx, dy, outline_scale);
  297.        }
  298. }
  299.  
  300. /* Add a (dx, dy) pair to the path being formed. */
  301. /* Accumulate successive segments in the same direction. */
  302. private int
  303. add_dxdy(register status *out, int dx, int dy, int count)
  304. {    int code;
  305.     if ( count != 0 )
  306.        {    if ( dx == out->dx && dy == out->dy )
  307.             out->count += count;
  308.         else
  309.            {    if ( out->count != 0 )
  310.                 put_deltas(out, out->dx * out->count,
  311.                        out->dy * out->count, 0);
  312.             out->dx = dx, out->dy = dy;
  313.             out->count = count;
  314.            }
  315.        }
  316.     return 0;
  317. }
  318.  
  319. /* Encode a (dx, dy) pair onto the path. */
  320. /* If there isn't enough space, return -1. */
  321. private int
  322. put_dxdy(register status *out, int dx, int dy, int moving)
  323. {    int code;
  324.     /* We do the arithmetic in the 1/4-pixel coordinate system, */
  325.     /* and then transform the result, to avoid accumulating */
  326.     /* rounding errors. */
  327.     int npx = out->px + dx, npy = out->py + dy;
  328.     gs_point npt;
  329.     int ncpx, ncpy;
  330.     int cdx, cdy;
  331.     gs_distance_transform((floatp)npx, (floatp)npy, &out->ifm, &npt);
  332.     ncpx = round_coord(npt.x);
  333.     ncpy = round_coord(npt.y);
  334.     cdx = ncpx - out->cpx;
  335.     cdy = ncpy - out->cpy;
  336. #ifdef DEBUG
  337. if ( gs_debug['0'] )
  338.     dprintf8("[0]  pxy=(%d,%d)+(%d,%d)  cpxy=(%d,%d)+(%d,%d)\n",
  339.          out->px, out->py, dx, dy, out->cpx, out->cpy, cdx, cdy);
  340. #endif
  341.     if ( cdx != 0 || cdy == 0 )    /* encode dx if needed */
  342.       if ( (code = put_int(out, cdx)) < 0 ) return code;
  343.     if ( cdy != 0 )            /* encode dy if needed */
  344.       if ( (code = put_int(out, cdy)) < 0 ) return code;
  345.     if ( out->next == out->limit ) return_error(gs_error_limitcheck);
  346.     *out->next++ = (byte)
  347.         (cdy == 0 ?        /* use hmove/lineto */
  348.             (moving ? c_hmoveto : c_hlineto) :
  349.         cdx == 0 ?        /* use vmove/lineto */
  350.             (moving ? c_vmoveto : c_vlineto) :
  351.         (moving ? c_rmoveto : c_rlineto));
  352.     out->px = npx, out->py = npy;
  353.     out->cpx = ncpx, out->cpy = ncpy;
  354.     return 0;
  355. }
  356.  
  357. /* Round a floating point coordinate.  If it is out of range, */
  358. /* return a limiting value. */
  359. private int
  360. round_coord(floatp v)
  361. {    long c = (long)(v + 0.5);
  362.     return( c > 0x7fff ? 0x7fff :
  363.         c < -0x7fff ? -0x7fff :
  364.         (int)c );
  365. }
  366. /* Encode a single number in Type 1 representation. */
  367. private int
  368. put_int(status *out, register int v)
  369. {
  370. #define min_enc_num1 ((c_min_num - c_max_num1) / 2)
  371. #define max_enc_num1 ((c_max_num1 - c_min_num) / 2)
  372. #define min_enc_num2 (max_enc_num1 + 1)
  373. #define max_enc_num2 (min_enc_num2 + (c_max_num2 - c_max_num1) * 256 - 1)
  374. #define min_enc_num3 (-max_enc_num2)
  375. #define max_enc_num3 (-min_enc_num2)
  376.     register byte *ptr = out->next;
  377.     if ( ptr + 5 > out->limit )    /* conservative test is faster */
  378.         return_error(gs_error_limitcheck);
  379.     if ( v >= min_enc_num1 && v <= max_enc_num1 )
  380.         *ptr++ = v - min_enc_num1 + c_min_num;
  381.     else if ( v >= min_enc_num2 && v <= max_enc_num2 )
  382.        {    v -= min_enc_num2;
  383.         *ptr++ = (v >> 8) + c_max_num1+1;
  384.         *ptr++ = v & 0xff;
  385.        }
  386.     else if ( v >= min_enc_num3 && v <= max_enc_num3 )
  387.        {    v = -(v - max_enc_num3);
  388.         *ptr++ = (v >> 8) + c_max_num2+1;
  389.         *ptr++ = v & 0xff;
  390.        }
  391.     else
  392.        {    *ptr++ = c_max_num3+1;
  393.         *ptr++ = ((long)v >> 24) & 0xff;
  394.         *ptr++ = ((long)v >> 16) & 0xff;
  395.         *ptr++ = (v >> 8) & 0xff;
  396.         *ptr++ = v & 0xff;
  397.        }
  398.     out->next = ptr;
  399.     return 0;
  400. }
  401.